package com.liuzhilong.infrastructure.framework.algorithms.algorithms.lrucache;

import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * <h1>lru cache</h1>
 * 实现一个lru cache。
 * 思路-使用一个链表维护key的使用记录。当key使用的时候，key放在最后，如果存储满了。删除头一个。
 *
 */
public class LRUCache {

    Map<Integer,Integer> holder = new LinkedHashMap<>();

    Deque<Integer> keysInfo = new LinkedList<>();

    private int capacity;


    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if(keysInfo.contains(key)){
            //获取并放在最后
            keysInfo.remove(key);
            keysInfo.addLast(key);
        }
        return holder.containsKey(key)? holder.get(key) :-1 ;
    }

    public void put(int key, int value) {
        holder.put(key,value);
        if(keysInfo.contains(key)){
            //获取并放在最后
            keysInfo.remove(key);
            keysInfo.addLast(key);
        }else{
            if (keysInfo.size()>=capacity) {
                holder.remove(keysInfo.removeFirst());
            }
            keysInfo.addLast(key);
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

        cache.put(1, 1);
        cache.put(2, 2);
        cache.get(1);       // 返回  1
        cache.put(3, 3);    // 该操作会使得密钥 2 作废
        cache.get(2);       // 返回 -1 (未找到)
        cache.put(4, 4);    // 该操作会使得密钥 1 作废
        cache.get(1);       // 返回 -1 (未找到)
        cache.get(3);       // 返回  3
        cache.get(4);       // 返回  4

    }
}
